package master;

import java.util.ArrayList;
import java.util.List;

/**
 * @author chenyw
 * @date 2022/7/28 15:19
 */
public class M74searchMatrix {
    //二分 O(log(m) + log(n))
    //因为每一行和每一列元素都是有序的，所有可以通过二分先定位行，再定位列
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = binarySearchColumn(matrix, target);
        if (row < 0) {
            return false;
        }
        return binarySearchRow(matrix[row], target);
    }

    private boolean binarySearchRow(int[] row, int target) {
        int j = row.length - 1;
        int i = 0;
        while (i <= j) {
            int mid = (j - i) / 2 + i;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return false;
    }

    private int binarySearchColumn(int[][] matrix, int target) {
        int low = -1;
        int high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }



/*    //O(m+n)复杂度
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = m - 1;
        int j = 0;
        while (i >= 0 && j < n) {
            while (i >= 0 && matrix[i][j] > target) {
                i--;
            }
            if (i < 0) {
                return false;
            }
            while (j < n) {
                if (matrix[i][j] == target) {
                    return true;
                } else if (matrix[i][j] > target){
                    return false;
                }
                j++;
            }
        }
        return false;
    }*/
}
